package 力扣日常刷题.木22一月.第13天0121;

/**
 * @author 帅小伙
 * @date 2022/1/21
 * @description 球当前的位置依赖与上一层的位置  以及上一层的状态
 * f(x) = f(f(x-1))
 */
public class Demo44动态规划球会落在何处 {

    public int[] findBall(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            ans[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ans[j] == -1) continue; // 以及卡住
                // 右拐
                if (grid[i][ans[j]] == 1 && ans[j] + 1 < m && grid[i][ans[j] + 1] == 1) {
                    ans[j]++;
                } else if (grid[i][ans[j]] == -1 && ans[j] - 1 >= 0 && grid[i][ans[j] - 1] == -1) {
                    ans[j]--;
                } else {
                    ans[j] = -1;
                }
            }
        }
        return ans;
    }


}
